package excercise.dynamic;

/**
 * 终于，破解了千年的难题。小 FF 找到了王室的宝物室，里面堆满了无数价值连城的宝物。
 * <p>
 * 这下小 FF 可发财了，嘎嘎。但是这里的宝物实在是太多了，小 FF 的采集车似乎装不下那么多宝物。看来小 FF 只能含泪舍弃其中的一部分宝物了。
 * <p>
 * 小 FF 对洞穴里的宝物进行了整理，他发现每样宝物都有一件或者多件。他粗略估算了下每样宝物的价值，之后开始了宝物筛选工作：小 FF 有一个最大载重为
 * W
 * W 的采集车，洞穴里总共有
 * n
 * n 种宝物，每种宝物的价值为
 * v
 * i
 * v
 * i
 * ​
 * ，重量为
 * w
 * i
 * w
 * i
 * ​
 * ，每种宝物有
 * m
 * i
 * m
 * i
 * ​
 * 件。小 FF 希望在采集车不超载的前提下，选择一些宝物装进采集车，使得它们的价值和最大。
 * <p>
 * 输入格式
 * 第一行为一个整数
 * n
 * n 和
 * W
 * W，分别表示宝物种数和采集车的最大载重。
 * <p>
 * 接下来
 * n
 * n 行每行三个整数
 * v
 * i
 * ,
 * w
 * i
 * ,
 * m
 * i
 * v
 * i
 * ​
 * ,w
 * i
 * ​
 * ,m
 * i
 * ​
 * 。
 * <p>
 * 输出格式
 * 输出仅一个整数，表示在采集车不超载的情况下收集的宝物的最大价值。
 * <p>
 * 输入输出样例
 * 输入 #1复制
 * 4 20
 * 3 9 3
 * 5 9 1
 * 9 4 2
 * 8 1 3
 * 输出 #1复制
 * 47
 * 说明/提示
 * 对于
 * 30
 * %
 * 30% 的数据，
 * n
 * ≤
 * ∑
 * m
 * i
 * ≤
 * 1
 * 0
 * 4
 * n≤∑m
 * i
 * ​
 * ≤10
 * 4
 * ，
 * 0
 * ≤
 * W
 * ≤
 * 1
 * 0
 * 3
 * 0≤W≤10
 * 3
 * 。
 * <p>
 * 对于
 * 100
 * %
 * 100% 的数据，
 * n
 * ≤
 * ∑
 * m
 * i
 * ≤
 * 1
 * 0
 * 5
 * n≤∑m
 * i
 * ​
 * ≤10
 * 5
 * ，
 * 0
 * ≤
 * W
 * ≤
 * 4
 * ×
 * 1
 * 0
 * 4
 * 0≤W≤4×10
 * 4
 * ，
 * 1
 * ≤
 * n
 * ≤
 * 100
 * 1≤n≤100。
 */
public class LuoGu_P1776 {
    public int solution(int w, int[] ci, int[] vi, int[] mi) {
        int[][] dp = new int[ci.length + 1][w + 1];
        for (int i = 1; i <= ci.length; i++) {
            for (int j = 1; j <= w; j++) {
                dp[i][j] = dp[i - 1][j];
                for (int k = 1; k <= mi[i - 1]; k++) {
                    if (j - k * ci[i - 1] >= 0) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * ci[i - 1]] + k * vi[i - 1]);
                    }
                }
            }
        }
        return dp[ci.length][w];
    }

    /**
     * 枚举优化
     *
     * @param w
     * @param ci
     * @param vi
     * @param mi
     * @return
     */
    public int solution2(int w, int[] ci, int[] vi, int[] mi) {
        int[] c2i = new int[1000];
        int[] v2i = new int[1000];

        int m = 0, cnt;

        for (int i = 0; i < ci.length; i++) {
            cnt = mi[i];
            for (int j = 1; j <= cnt; j <<= 1) {
                c2i[++m] = j * ci[i];
                v2i[m] = j * vi[i];
                cnt -= j;
            }
            if (cnt > 0) {
                c2i[++m] = cnt * ci[i];
                v2i[m] = cnt * vi[i];
            }
        }

        return f(w, m, c2i, v2i);
    }

    public int f(int w, int m, int[] ci, int[] vi) {
        int[][] dp = new int[m + 1][w + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 0; j <= w; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j - ci[i] >= 0) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - ci[i]] + vi[i]);
                }
            }
        }
        return dp[m][w];
    }

    public static void main(String[] args) {
        int w = 20;
        int[] ci = {9, 9, 4, 1};
        int[] vi = {3, 5, 9, 8};
        int[] mi = {3, 1, 2, 3};

        int solution = new LuoGu_P1776().solution(w, ci, vi, mi);
        // int solution = new LuoGu_P1776().solution2(w, ci, vi, mi);
        System.out.println("solution = " + solution);
    }
}
